package com.zk.algorithm.array;

import com.zk.algorithm.Utils;

import java.util.Random;

/**
 * 洗牌算法 https://xiaozhuanlan.com/topic/3890452617
 *
 * Fisher–Yates shuffle
 *
 * 每次从一组数中随机选出一个数，然后与最后一个数交换位置，并且不再考虑最后一个数
 *
 * @author zk
 */
public class ShuffleArray {

    public static void main(String...args) {
        Utils.println(ShuffleArray.shuffle(new int[]{1, 2, 3, 4, 5, 6}));
    }

    //
    // 如何测试
    //
    // https://coolshell.cn/articles/8593.html
    // 设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内
    //
    public static final int[] shuffle(int[] nums) {
        Random random = new Random();

        //
        // ←----------------
        //
        // 1, 2, 3, 4, 5, 6
        //                ↑
        //                i
        //       ↑
        //       j
        //
        // 1, 2, 6, 4, 5, 3
        //             ↑
        //             i
        //          ↑
        //          j
        // 1, 2, 6, 5, 4, 3
        //
        for (int i = nums.length - 1; i >= 0; i--) {
            int j = random.nextInt(i + 1); // [0,i]
            Utils.swap(nums, i, j);
        }

        return nums;
    }

}
